//摆动序列
class Solution {
    public:
        int wiggleMaxLength(vector<int>& nums) {
            int n = nums.size();
            if(n < 2) return n;
            vector<int> up(n,1),down(n,1);
            int ret = 0;
            for(int i = 1; i < n; i++)
            {
                for(int j = 0; j < i; j++)
                {
                    if(nums[i] > nums[j]) up[i] = max(down[j] + 1,up[i]);
                    else if(nums[i] < nums[j]) down[i] = max(up[j] + 1,down[j]);
                }
                ret = max(up[i],down[i]);
            }
            return ret;
        }
    };


    class Solution {
        public:
            int wiggleMaxLength(vector<int>& nums) {
                int n = nums.size();
                if(n < 2) return n;
                vector<int> dp(n,1);
                if(nums[0] != nums[1])
                {
                    dp[0] = 1,dp[1] = 2;
                }else{
                    dp[0] = dp[1] = 1;
                }
                for(int i = 1; i < n; i++)
                {
                    for(int j = 1; j < i;j++)
                    {
                        if((nums[i] < nums[j] && nums[j] > nums[j-1])
                        ||(nums[i] > nums[j] && nums[j] < nums[j-1]))
                        {
                            dp[i] = max(dp[j]+1,dp[i]);
                        }
                    }
                    if(dp[i] == 1 && nums[i] != nums[i-1])
                    {dp[i] = 2;}
                }
                for(auto& e : dp)
                {
                    cout << e << " ";
                }
                return *std::max_element(dp.begin(),dp.end());
            }
        };